#coding:utf-8
'''
递归：自己调用自己的方法，称为递归
'''

'''
1+2+3+4+5...+100 用递归实现
'''
def fa(n):
    if(n==1):
        return 1
    else:
        return n+fa(n-1)
#print(fa(100))

'''
有一对兔子，从第三个月开始每一个月生另一对兔子，
新兔子从第三个月开始每一个月生另一对兔子
假设兔子不死，问第12个月兔子的数量
1   1                      1
2   1                      1
3   1 + 1                  2
4   1 + 1 + 1              3
5   1 + 1 + 1 + 1 + 1      5
6...1 + 1 + 1 + 1 + 1 + 3  8
...
12                         ?
1 1 2 3 5 8 13 21 34 
'''
def rab(a):
    if a==1 or a==2:
        return 1
    else:
        return rab(a-1)+rab(a-2)
#print(rab(12))


'''
快速排序：递归实现排序
      4 75 7  2      12        33 25
      4 7 2         12         75 33 25
      4 2 7  
      2 4 7          12            25  33  75
'''
def fast_sort(a):
    if(len(a)>=2):
        #找基准数
        mid = a[len(a)//2] #随便，哪个都行
        left,right = [],[]  #定义两个列表
        a.remove(mid)  #把基准数移除
        for num in a:
            if num > mid:
                right.append(num) #大的放右边
            else:
                left.append(num) #小的放左边
        return fast_sort(left) + mid + fast_sort(right)        
    else:
        return a









